import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // int[] nums = new int[]{3,6,9,12};
        // System.out.println(test.longestArithSeqLength(nums));

        int[] nums = new int[]{7,7,7,7,7};
        System.out.println(test.numberOfArithmeticSlices(nums));
    }

    public int longestArithSeqLength(int[] nums) {
        /***
         * 最长等差数列
         * 状态表示：
         *  dp[i][j]表示以i j下标元素为结尾的所有子序列中，最长等差子序列的长度，并规定i<j
         * 状态转移方程：
         *  前一个值的下标必须合法
         *  if(nums[j]-nums[i]存在) {
         *      dp[i][j] = dp[k][i] + 1;
         *  }
         * 初始化：
         *  由状态表示可知，其已经存在两个元素，故最差值为2，使用2填充全表
         * 填表顺序：
         *  从左到右，从上到下
         * 返回值：
         *  dp表中的最大值（不知道2算不算，若是2不算，则为0）==>本题中规定，随意两个值也构成等差子序列，长度为2
         */
        // 1 预处理
        int n = nums.length;
        // 2 创建dp表
        int[][] dp = new int[n][n];
        Map<Integer, Integer> map = new HashMap<>();
        // 3 初始化
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        map.put(nums[0], 0);
        // 4 填表
        int maxLength = 2;
        for(int i = 1; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                // -t为公差，因此我们找前一个值应当为 nums[i] - t
                int t = nums[j] - nums[i];
                if(map.containsKey(nums[i] - t)) {
                    dp[i][j] = dp[map.get(nums[i] - t)][i] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
            // -i步进时，添加新值入map中
            map.put(nums[i], i);
        }
        // 5 返回值
        return maxLength;
    }

    public int numberOfArithmeticSlices(int[] nums) {
        /**
         * 等差数列划分Ⅱ -子序列
         * 状态表示：
         *  dp[i][j]表示以i下标元素 与 j下标元素为结尾的所有子序列中，等差子序列的数目
         * 状态转移方程：
         *  if(nums[j] - nums[i] 存在) {
         *      dp[i][j] = dp[k][i] + 1;
         *  }
         * 初始化：
         *  全部初始化为2
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  dp表中所有值之和
         * */
        // 1 预处理
        int n = nums.length;
        // 2 创建dp表
        int[][] dp = new int[n][n];
        Map<Long, ArrayList<Integer>> map = new HashMap<>();
        // 3 初始化
        //        for(int i = 0; i < n; i++) {
        //            for(int j = 0; j < n; j++) {
        //                dp[i][j] = 2;
        //            }
        //        }
        // -使用数组进行存储下标，这样才能把所有符合条件的值统计
        ArrayList<Integer> tempList = new ArrayList<>();
        tempList.add(0);
        map.put((long)nums[0], tempList);
        // 4 填表
        int maxAmount = 0;
        for(int i = 1; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                long t = (long)nums[i] - ((long)nums[j] - nums[i]);
                // -前值若是存在，对已遍历区域中所有目标值进行统计
                if(map.containsKey(t)) {
                    for(int k: map.get(t)) {
                        dp[i][j] += dp[k][i] + 1;
                    }
                    maxAmount += dp[i][j];
                }
            }
            // -将新值添加至集合中
            if(map.containsKey((long)nums[i])) {
                map.get((long)nums[i]).add(i);
            } else {
                tempList = new ArrayList<>();
                tempList.add(i);
                map.put((long)nums[i], tempList);
            }
        }
        // 打印dp表查看结果
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        // 5 返回值
        return maxAmount;
    }
}
